package LimitedTimeGame.Day_0214;

/**
 * @author zxc
 * @date 2023/02/14 11:43
 **/

import java.util.Arrays;
import java.util.HashMap;
import java.util.Stack;

/**
 * 题目 ：表现良好的最长时间段
 * 题目详述 ：
 * 给你一份工作时间表hours，上面记录着某一位员工每天的工作小时数。
 * 我们认为当员工一天中的工作小时数大于8 小时的时候，那么这一天就是「劳累的一天」。
 * 所谓「表现良好的时间段」，意味在这段时间内，「劳累的天数」是严格 大于「不劳累的天数」。
 * 请你返回「表现良好时间段」的最大长度。
 *
 * 提示：
 * 1 <= hours.length <= 104
 * 0 <= hours[i] <= 16
 *
 */
public class LongestWPI02 {
    /**
     * 思路 ：
     * ===>
     * 由于员工的工作天数，以每天工作小时数八小时为分界线，被划分为[劳累的一天] || [普通的一天]
     * （1）即，将所有[劳累的一天]都重定义为1，[普通的一天]则是被重定义为-1;
     *  ===》 该问题转化为，求解hours数组中，满足（子数组之和 > 0）条件的最长子数组;
     * （2）求解hours数组的前缀和（即，第0个元素 - 第i个元素之和） && 同时，使用辅助数值dp对其值进行存储;
     *  注意 ：dp[0]的值为0，代表未存储任何hours数组中元素;
     *  ===> 即，若是要求数组hours中 第i个元素 - 第j个元素之和的话，即dp[j + 1] - dp[i + 1];
     *
     *
     * @param hours
     * @return
     */
    public int longestWPI(int[] hours) {
        int len = hours.length;
        int[] dp = new int[len + 1];
        for(int i = 0 ; i < len ; i++){
            System.out.println(dp[i]);
            dp[i + 1] = dp[i] + (hours[i] > 8 ? 1 : -1);
        }

        int max = 0;
        // 1.暴力遍历所有可能性
        // 结果 ：超时报错;
//        for(int i = 0 ; i < len ; i++){
//            for(int j = i + 1 ; j <= len ; j++){
//                System.out.println(dp[j]);
//                if(dp[j] > dp[i]){
//                    max = Math.max(max , j - i);
//                }
//            }
//        }

        // 优化一 ：对于内层for循环进行优化，
        // 即，从后向前遍历，若是在遍历过程中，寻找到符合条件的子数组，那么直接结束内层循环即可;
        // 由于当前遍历的连续子数组最左元素是固定的，从后遍历是逐步将子数组长度减少;
        // 结果 ： 只能够通过一部分示例，极有可能会导致超时；
//        for(int i = 0 ; i < len ; i++){
//            for(int j = len ; j > i ; j--){
//                System.out.println(dp[j]);
//                if(dp[j] > dp[i]){
//                    max = Math.max(max , j - i);
//                    break;
//                }
//            }
//        }

        // 优化二 ：对于外层for循环进行优化，
        /**
         * 如何理解对于外层for循环的优化
         * ===》
         * （1）首先，在连续子数组最左元素下标为i的情况下，内层for循环遍历获取最长连续子数组的最右元素下标为j（dp[j] > dp[i]）;
         *  ===》 即，代表了在数组dp中，下标为j的右边元素k，皆不满足条件dp[k] > dp[i];
         *  即，代表了dp[j] > dp[k] && dp[k] < dp[i];
         *
         * （2）i < i1 < j的情况下，
         *  a.若是dp[i1] > dp[i]（单调递增）,由于dp[k] < dp[i],所以dp[i1] > dp[k];
         *  ===> 即，所求解出来连续子数组长度必然小于 j - i;
         *  b.若是dp[i1] < dp[i]（单调递减）,则有可能出现的dp[i1] < dp[k]的情况，从而能够求解出更长的连续子数组;
         *
         * （3）总结 ：
         *  由于从 0 开始，所以外层for循环遍历的数字，需要满足单调递减;
         *
         */
        Stack<Integer> stack = new Stack<>();
        stack.push(0);
        for(int i = 1 ; i <= len ; i++) {
             if(dp[i] < dp[stack.peek()]){
                 stack.push(i);
             }
        }
        while(!stack.isEmpty()){
            Integer popValue = stack.pop();
            for(int j = len ; j > popValue ; j--){
                System.out.println(dp[j]);
                if(dp[j] > dp[popValue]){
                    max = Math.max(max , j - popValue);
                    break;
                }
            }
        }
        return max;
    }

}

